class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        """TLE
        """
        def reverse(n, length):
            MAX = 2**length - 1
            for i in range(length // 2):
                highTemp = 1 << (length - (i + 1))
                res = highTemp & n
                high = 0 if res == 0 else 1
                lowTemp = 1 << i
                res = lowTemp & n
                low = 0 if res == 0 else 1
                if high == 1 and low == 0:
                    n += lowTemp
                    n &= (MAX ^ highTemp)
                elif high == 0 and low == 1:
                    n &= (MAX ^ lowTemp)
                    n += highTemp

            return n

        if k == 1:
            return '0'
        num = 0
        for i in range(2, n + 1):
            s = 2**(i - 1)
            second = num ^ (2**(s - 1) - 1)
            second = reverse(second, s - 1)
            mid = 1 << (s - 1)
            first = num << (s)
            num = first + mid + second
        length = 2**n - 1
        diff = length - k
        mark = 1 << diff
        res = num & mark

        return '0' if res == 0 else '1'
